#ifndef _CQUEUE_
#define _CQUEUE_

#include <deque>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

static const auto io_sync_off = []() {
    // turn off sync
    ios::sync_with_stdio( false );

    // turn off binding of cin and cout
    cin.tie( nullptr );
    cout.tie( nullptr );
    return nullptr;
}();

class CQueue {
public:
    CQueue() {}

    // mycode
    void appendTail_M( int value ) {
        if ( a.empty() && b.empty() ) {
            a.push( value );
        }
        else {
            while ( !a.empty() ) {
                b.push( a.top() );
                cout << " b" << a.top() << " ";
                a.pop();
            }
            a.push( value );
            while ( !b.empty() ) {
                a.push( b.top() );
                cout << " a" << b.top() << " ";
                b.pop();
            }
        }
    }

    int deleteHead_M() {
        if ( a.empty() && b.empty() ) {
            return -1;
        }

        int x = a.top();
        a.pop();
        return x;
    }

    // standard answer
    void appendTail( int value ) {
        a.push( value );
    }

    int deleteHead() {
        if ( a.empty() && b.empty() ) {
            return -1;
        }
        if ( b.empty() ) {
            while ( !a.empty() ) {
                b.push( a.top() );
                a.pop();
            }
        }
        int x = b.top();
        b.pop();
        return x;
    }

private:
    std::stack< int > a;  // IN
    std::stack< int > b;  // OUT
};

class MaxQueue {
public:
    MaxQueue() {}

    int max_value() {
        if ( queue.empty() ) {
            return -1;
        }
        return deque.front();
    }

    void push_back( int value ) {

        if ( queue.empty() ) {
            queue.push( value );
            deque.push_back( value );
        }
        else {
            queue.push( value );

            while ( !deque.empty() && value > deque.back() ) {
                deque.pop_back();
            }
            deque.push_back( value );
        }
        return;
    }

    int pop_front() {
        if ( queue.empty() ) {
            return -1;
        }
        int a = queue.front();
        queue.pop();

        if ( a == deque.front() ) {
            deque.pop_front();
        }

        return a;
    }

private:
    queue< int > queue;
    deque< int > deque;
};

#endif /*_CQUEUE_*/